三个经典排序算法

面试常聊的几个排序算法，总结整理一下，

堆排序

目前感觉，最有趣也最有挑战的排序
思路：

将数组视为完全二叉树，其父子关系使用下标确定，
root -> left
arr[left] = arr[root * 2 +1] (下标从0开始哈)
构建大根堆, 所有的二叉树都满足
根节点 > ( 左节点 | 右节点 )

将一个数组构建成一个大根堆，具体操作（堆化操作）
假设左右子树都是大根堆，
则选择左右节点较大的，与根节点比较：
若是小于根节点，符合要求，返回
若是大于根节点，则交换根节点和该节点
交换后，该子树需要继续 堆化操作，直至到以下所有子树都符合要求

堆化操作的前提是需要其子树都符合堆的要求，
故，将一个源数组堆化，需要从底部的树开始，从下往上，从右往左，依次讲个所有的子树堆化，最后整个二叉树也就堆化了

堆化后，假设是大根堆，我们求其正序

第一个元素是最大元素，我们选择好该最大元素，与最后一个元素交换， 接着，继续堆化nums[0,n-2],num[n]已经排好序了
重复以上

可以看到, 堆排序是选择排序的优化哈

/**
 * 参考 https://www.cnblogs.com/chengxiao/p/6129630.html
 *
 * 堆排序，首先要求时完全二叉树，使用数组的存储结构，叶子节点只会在倒数第二层出现
 * 大根堆，节点值均小于根节点
 * 使用数组存储结构时，根节点与子节点关系可以通过下标换算的，arr[left] = arr[root*2+1] , arr[right] = arr[root*2+2]
 *
 *
 */
object HeapSort {
    fun heapSort(arr: IntArray) {
//        val arr = intArrayOf(4, 6, 8, 5, 9)
        arr.println()
        val len = arr.size
        for (i in len / 2 - 1 downTo 0) {
            adjustHeap(arr, i, len)
        }
        for (k in len - 1 downTo 0) {
            arr.swap(0, k)
            adjustHeap(arr, 0, k)
        }
        arr.println()
    }

    //以firstRoot开始，使得该节点为最大值
    //注意该调整有个前提，其左右子树已经是个大根堆了
    //故，初始化一个大根堆，则需要最后一个非叶子节点开始，从下往上，从左往右迭代调整
    private fun adjustHeap(arr: IntArray, firstRoot: Int, len: Int) {
        var root = firstRoot
        val max = arr[firstRoot]    //其实我们就是要找最大的元素
        var k = 0
        do {
            k = root * 2 + 1
            if (k < len) {
                //要找到左右节点中较大的哦
                if (k + 1 < len && arr[k] < arr[k + 1]) {
                    k++
                }
                if (arr[k] > max) {    //若是存在叶子节点比root大的情况
                    arr[root] = arr[k]
                    root = k    //root指向该叶子节点，继续循环以该root为节点的树
                } else {
                    break
                }
            }
        } while (k < len)
        arr[root] = max
    }


}

快排

思路：
选择一个中轴，将一个数组分为两部分，使得左边比中轴小，右边比中轴大
实际操作中，将第左边界的第一个值设为中轴，迭代访问后面的元素，若是发现比中轴小，则将该元素插入到中轴左侧

针对左右两部分，递归使用以上操作，递归终止在，对应操作的数组只有一个元素时。

时间复杂度，递归深度是log₂n故，时间复杂度是 nlog₂n 空间复杂度，递归使用了栈空间，故 log₂n

object QuickSort {

    fun quickSort(nums: IntArray) {
        helper(nums, 0, nums.size - 1)
    }

    private fun helper(nums: IntArray, left: Int, right: Int) {
        if (left >= right) {
            return
        }
        var pivot = left
        var start = left + 1
        var end = right
        while (start <= end) {
            println("pivot:${nums[pivot]},check ${nums[start]}")
            if (nums[start] < nums[pivot]) {
                //把当前数插入到左端
                moveToHead(nums, left, start)
                //轴也会右移
                pivot++
            }
            start++
        }
        //每一遍结束，pivot都能划分[left,right]
        nums.println()

        helper(nums, left, pivot - 1)
        helper(nums, pivot + 1, right)
    }

    //将数组翻转一位
    //这里效率很低啊
    private fun moveToHead(nums: IntArray, left: Int, right: Int) {
        val temp = nums[right]
        for (i in right downTo left + 1) {
            nums[i] = nums[i - 1]
        }
        nums[left] = temp
    }
    
    //
}

append: 避免移动元素的快排，

static void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int i = start, j = end;
    // 将中轴取出来，将其保存至变量pivot,随之arr[i]这个坑空出来了
    int pivot = arr[start];
    while (i < j) {
        // 从右往左寻找第一个比中轴小的数，找到其
        while (i < j && arr[j] > pivot) {
            j--;
        }
        arr[i] = arr[j];
        // 同样，从左边开始，寻找第一个比中轴大的元素

        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
        System.out.println("i " + i + ", j " + j);
    }
    // 此时i == j
    arr[i] = pivot;
    quickSort(arr, start, i - 1);
    quickSort(arr, i + 1, end);
}

归并

思路：

1，拆分
针对数组，以下标中点将数组划分为左右两部分
针对左右两部分，重复以上操作，直至该数组只有一个元素，(递归出口，一个元素是有序的)

2，合并
将拆分的两个部分，两者都是有序数组，合并成一个有序数组
重复以上

关于合并两个有序数组的优化 取巧，若是第一个数组中最大的元素比第二数组中最小的元素还小，可直接拼接

LeetCode中相关的题目，求数组中的逆序对

object MergeSort {
    //另外，可以利用归并排序的稳定性，
    fun mergeSort(nums: IntArray) {
        val copy = nums.copyOf()
        helper(nums, copy, 0, nums.size - 1)
    }

    private fun helper(nums: IntArray, copy: IntArray, left: Int, right: Int) {
        if (left == right) {
            return
        }
        val mid = left + (right - left) / 2
        helper(nums, copy, left, mid)
        helper(nums, copy, mid + 1, right)
        mergeArr(nums, copy, left, mid, right)
    }

    // 合并两个有序的数组，为了避免每次都要创建一个字数组来保存，
    // 
    private fun mergeArr(nums: IntArray, copy: IntArray, left: Int, mid: Int, right: Int) {
        nums.println()
        println("mid:${nums[mid]}, left:${nums[left]}, right:${nums[right]}")

        // 依赖上一次合并状态
        for (i in left..right) {
            copy[i] = nums[i]
        }
        var i = left
        var j = mid + 1
        var k = left
        while (i <= mid && j <= right) {
            if (copy[i] <= copy[j]) {
                nums[k++] = copy[i++]
            } else {
                nums[k++] = copy[j++]
            }
        }
        while (i <= mid) {
            nums[k++] = copy[i++]
        }
        while (j <= right) {
            nums[k++] = copy[j++]
        }
    }
}

github代码